package com.atguigu.practice;

import java.util.Arrays;

public class TheImpossibleSum {
    public static void main(String[] args) {
        int[] a=new int[]{3,2,1};
        System.out.println(getFirstUnFormedNum(a));
    }
    //数组的不可组成和
        public  static int getFirstUnFormedNum(int[] arr) {
            Arrays.sort(arr); //排序数组
            int min = arr[0]; //获取最小值
            int max = 0; //获取最大值
            for (int k : arr) {
                max += k;
            }
            //创建布尔类型数组，存储[min,max]区间的每个值能否被组成
            boolean[] result = new boolean[max + 1];
            result[0] = true;
            for(int t : arr){
                for(int i = max;i >= t;i--){
                    result[i] = result[i - t] || result[i];
                }
            }
            //遍历result数组，找到第一个结果为false的数，表示不能被组成，即为最小不可组成和
            for(int j = min;j < result.length;j++){
                if(!result[j]){
                    return j;
                }
            }
            //循环结束没有输出，说明数组内所有的数都能被组成，那么就返回max+1
            return max+1;
        }
    }

